package 二叉树;

import static java.lang.Math.min;

public class LC_111二叉树的最小深度 {
    public class TreeNode {
        int val;
        LC_111二叉树的最小深度.TreeNode left;
        LC_111二叉树的最小深度.TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, LC_111二叉树的最小深度.TreeNode left, LC_111二叉树的最小深度.TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public int minDepth(TreeNode root) {
        //根节点到叶子结点的最小距离
        //前序求深度，后序求高度；前序略复杂，故可用后序求深度&高度
        if(root==null) return 0;
        int leftheight=minDepth(root.left);
        int rightheight=minDepth(root.right);
        //排除右子树为空
        if(root.left !=null && root.right ==null)
            return 1+leftheight;
        if(root.left ==null && root.right !=null)
            return 1+rightheight;
        return 1+min(rightheight,leftheight);
    }
}
